package main

import (
	"fmt"
	"go-study/algorithm/standard"
)

// 如何找出数组中唯一的重复元素
// 引申：对于一个给定的自然数 N，有一个 N+M 个元素的数组，其中存放了小于等于 N 的所有自然数，求重复出现的自然数序列{X}

func main() {
	arr := []int{1, 3, 4, 2, 5, 3}
	fmt.Println(findDupByHash(arr))
	fmt.Println(findDupByXOR(arr))
	//fmt.Println(findDupByMap(arr))
	fmt.Println(findDupByLoop(arr))

	arr2 := []int{1, 2, 3, 3, 3, 4, 5, 5, 5, 5, 6}
	set := findDup(arr2, 6)
	for _, v := range set.List() {
		fmt.Print(v.(int), " ")
	}
	fmt.Println()
}

// 方法一：哈希法
func findDupByHash(arr []int) int {
	if arr == nil {
		return -1
	}
	data := map[int]bool{}
	for _, v := range arr {
		if _, ok := data[v]; ok {
			return v
		} else {
			data[v] = true
		}
	}
	return -1
}

// 方法二：累加求和法

// 方法三：异或法
func findDupByXOR(arr []int) int {
	if arr == nil {
		return -1
	}
	result := 0
	length := len(arr)
	for _, v := range arr {
		result ^= v
	}
	for i := 1; i < length; i++ {
		result ^= i
	}
	return result
}

// 方法四：数据映射法
func findDupByMap(arr []int) int {
	if arr == nil {
		return -1
	}

	length := len(arr)
	index := 0
	i := 0
	for true {
		if arr[i] >= length {
			return -1
		}
		if arr[index] < 0 {
			break
		}

		arr[index] *= -1
		index = arr[index] * -1
		if index >= length {
			return -1
		}
	}

	return index
}

// 方法五：环形相遇法
func findDupByLoop(arr []int) int {
	if arr == nil {
		return -1
	}

	slow := 0
	fast := 0
	for ok := true; ok; ok = slow != fast {
		fast = arr[arr[fast]]
		slow = arr[slow]
	}

	fast = 0
	for ok := true; ok; ok = slow != fast {
		fast = arr[fast]
		slow = arr[slow]
	}

	return slow
}

// 引申
// 题目中说的是：数组中存放了小于等于 N 的所有自然数
// 所以数组中下标为 1 ~ N 个元素必定能被访问到，除非下标等于值且没有别的元素指向它
// 对于 N 以上的下标，我们需要一种方式来指向到它，比如遇到重复元素的时候指向
func findDup(arr []int, num int) *standard.Set {
	s := standard.NewSet()
	if arr == nil {
		return s
	}

	length := len(arr)
	index := arr[0]
	num--

	for true {
		// 遇到重复的数字时，跳转到那些不会由值跳转的地方去
		if arr[index] < 0 {
			num--
			arr[index] = length - num
			s.Add(index)
		}
		if num == 0 {
			return s
		}
		arr[index] *= -1
		index = arr[index] * -1
	}
	return s
}
